"""
kmp 算法
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html


    　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；

    　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

    　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

    　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

    　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

    　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

    　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

"""
class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle: return 0
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

    def str_kmp(self, haystack, needle):
        pnext, i, j = self.gen_pnext(needle), 0, 0
        n, m = len(haystack), len(needle)
        while j < n and i < m:
            if i == -1 or haystack[j] == needle[i]:
                j, i = j + 1, i + 1
            else:
                i = pnext[i]
        if i == m:
            return j - i
        return -1

    def gen_pnext(self, p):
        i, k, m = 0, -1, len(p)
        pnext = [-1] * m
        while i < m - 1:
            if k == -1 or p[i] == p[k]:
                i, k = i + 1, k + 1
                if p[i] == p[k]:
                    pnext[i] = pnext[k]
                else:
                    pnext[i] = k
            else:
                k = pnext[k]
        return pnext




s = Solution()
print(s.str_kmp("abcdabcy", "abcd"))